"""
40.组合总和II
https://leetcode.cn/problems/combination-sum-ii/description/

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

** candidates 中的每个数字在每个组合中只能使用一次。**

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
"""

import collections
from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.result = []
        candidates.sort()
            
        self.backtrack2(candidates, target, 0, [], 0)
        return self.result
    
    def backtrack(self, candidates, target, ind, path:List, sum):
        """
        回溯递归的是按path的长度决定递归的深度
        每次递归都要遍历所有候选值
        """
        for i in range(ind, len(candidates)):
            if sum + candidates[i] > target:
                continue
            # 跳过重复的数字
            # 重复的数字在上一层递归时就已经遍历了所有情况
            # 因此重复的数字必须连续入栈，出栈时会考虑数字少的情况
            if i>0 and candidates[i] == candidates[i-1]:
                for j in range(i-1, -1, -1):
                    if candidates[j] != candidates[i]:
                        break
                    else:
                        j = -1
                if len(path) < (i-1-j):
                    continue
                if path[-(i-1-j)] != candidates[i]:
                    continue
            if sum + candidates[i] == target:
                path.append(candidates[i])
                self.result.append(path[:])
                path.pop(-1)
                continue
            path.append(candidates[i])
            self.backtrack(candidates, target, i+1, path, sum+candidates[i])
            path.pop(-1)
    
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        freq = sorted(collections.Counter(candidates).items())
        self.ans = list()
        sequence = list()
        self.backtrack2(0, target, sequence, freq)
        return self.ans

    def backtrack2(self, pos: int, rest: int, sequence:List, freq):
        if rest == 0:
            self.ans.append(sequence[:])
            return
        if pos == len(freq) or rest < freq[pos][0]:
            return
        
        self.backtrack2(pos + 1, rest, sequence, freq)

        most = min(rest // freq[pos][0], freq[pos][1])
        for i in range(1, most + 1):
            sequence.append(freq[pos][0])
            self.backtrack2(pos + 1, rest - i * freq[pos][0], sequence, freq)
        sequence = sequence[:-most]

        

if __name__ == "__main__":
    candidates = [10,1,2,7,6,1,5]
    target = 8
    candidates = [2,5,2,1,2]
    target = 5
    
    s = Solution()
    ans = s.combinationSum2(candidates, target)
    print(ans)
    
    # 输出: [[2,2,2,2],[2,3,3],[3,5]]
        